package Demo9;

import java.util.Random;
import java.util.Scanner;

class TreeNode {
    int key;
    TreeNode left, right;

    public TreeNode(int key) {
        this.key = key;
        this.left = this.right = null;
    }
}

public class BinarySearchTree {
    private TreeNode root;
    private int comparisonCount = 0;
    private int isDuplicateInsert = 0;  // 用于检测是否存在重复插入

    // 插入节点
    public void insert(int key) {
        root = insertNode(root, key);
    }

    private TreeNode insertNode(TreeNode node, int key) {
        if (node == null) {
            node = new TreeNode(key);
        } else if (key < node.key) {
            node.left = insertNode(node.left, key);
        } else if (key > node.key) {
            node.right = insertNode(node.right, key);
        } else {
            isDuplicateInsert++;  // 表示重复插入
        }
        return node;
    }

    // 中序遍历
    public void inorderTraversal() {
        inorderTraversal(root);
        System.out.println();
    }

    private void inorderTraversal(TreeNode node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.print(node.key + " ");
            inorderTraversal(node.right);
        }
    }

    // 查找节点
    public TreeNode search(TreeNode node, int key) {
        comparisonCount++;
        if (node == null || key == node.key) {
            return node;
        }
        if (key < node.key) {
            return search(node.left, key);
        } else {
            return search(node.right, key);
        }
    }

    // 删除节点
    public TreeNode delete(TreeNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                TreeNode minNode = findMin(node.right);
                node.key = minNode.key;
                node.right = delete(node.right, minNode.key);
            }
        }
        return node;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 生成随机整数
    public static int getRand(int min, int max) {
        Random rand = new Random();
        return rand.nextInt(max - min + 1) + min;
    }

    // 构建二叉搜索树
    public void createBST(int min, int max, int num) {
        root = null;
        for (int i = 0; i < num; i++) {
            int e = getRand(min, max);
            System.out.print(e + " ");
            insert(e);
        }
        System.out.println();
    }

    public TreeNode getRoot() {
        return root;
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        while (flag) {
            System.out.println("*************************************");
            System.out.println("*        1.建立随机二叉树             ");
            System.out.println("*        2.输出二叉树【中序遍历】   ");
            System.out.println("*        3.插入数据                 ");
            System.out.println("*        4.查找【同时输出比较次数】 ");
            System.out.println("*        5.删除数据                 ");
            System.out.println("*        0.退出                     ");
            System.out.println("*************************************");
            int choose = scanner.nextInt();
            switch (choose) {
                case 1:
                    System.out.println("请输入你要生成的随机整数的个数: ");
                    int num = scanner.nextInt();
                    System.out.println("请输入建立随机二叉树整数序列的范围（依次输入下限和上限）：");
                    int minN = scanner.nextInt();
                    int maxN = scanner.nextInt();
                    bst.createBST(minN, maxN, num);
                    System.out.println("随机二叉树建立成功！");
                    break;
                case 2:
                    System.out.println("中序遍历结果：");
                    bst.inorderTraversal();
                    break;
                case 3:
                    System.out.println("请输入要插入的数据：");
                    int key = scanner.nextInt();
                    bst.isDuplicateInsert = 0;
                    bst.insert(key);
                    if (bst.isDuplicateInsert == 0) {
                        System.out.println("数据" + key + "插入成功！");
                    } else {
                        System.out.println("该数据节点已存在！");
                    }
                    break;
                case 4:
                    bst.comparisonCount = 0;
                    System.out.println("请输入要查找的数据：");
                    key = scanner.nextInt();
                    TreeNode result = bst.search(bst.getRoot(), key);
                    if (result != null) {
                        System.out.println("成功查到数据" + result.key);
                        System.out.println("比较次数为：" + bst.comparisonCount);
                    } else {
                        System.out.println("您所查询的数据不存在！");
                    }
                    break;
                case 5:
                    System.out.println("请输入要删除的数据：");
                    key = scanner.nextInt();
                    bst.root = bst.delete(bst.getRoot(), key);
                    System.out.println("数据为" + key + "的节点已成功被删除！");
                    break;
                case 0:
                    System.out.println("确定退出吗？（Y/N）");
                    char exitConfirm = scanner.next().charAt(0);
                    if (exitConfirm == 'Y' || exitConfirm == 'y') {
                        flag = false;
                    }
                    break;
                default:
                    System.out.println("该选择不存在，请重新输入！");
                    break;
            }
        }
        scanner.close();
    }
}
